package main

import (
	"strconv"
)

//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
//
//
//
// 进阶：
//
// 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
//
//
//
// 示例：
//
// 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 8 -> 0 -> 7
//
// Related Topics 链表
// 👍 316 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
    Val int
    Next *ListNode
}

// 将一个整数转换为 ListNode
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// 思路: 将两个连表中的每个节点的数保存到数组中.
	l1ArrLen := 0
	l2ArrLen := 0

	l1New := l1
	l2New := l2
	for l1 != nil {
		l1ArrLen++
		l1 = l1.Next
	}

	for l2 != nil {
		l2ArrLen++
		l2 = l2.Next
	}

	maxLen := l1ArrLen
	if l2ArrLen > l1ArrLen {
		maxLen = l2ArrLen
	}


	l1Arr := make([]int, maxLen)
	l2Arr := make([]int, maxLen)

	// 填充两个数组
	i := 0
	for l1New != nil {
		l1Arr[l1ArrLen - i - 1] = l1New.Val
		l1New = l1New.Next
		i++
	}

	j := 0
	for l2New != nil {
		l2Arr[l2ArrLen - j - 1] = l2New.Val
		l2New = l2New.Next
		j++
	}

	// 计算两个数组中对应为的和

	retArr := make([]int, maxLen + 1)
	carry := 0
	for i := 0; i < maxLen; i++ {
		sum := l1Arr[i] + l2Arr[i]  + carry
		carry = sum / 10
		sum = sum % 10
		retArr[i] = sum
	}

	retArr[maxLen] = carry

	// 将数组装换为连表
	ll := &ListNode{}
	lt := ll

	for i := maxLen; i >=0; i-- {
		if i == maxLen && retArr[i] == 0 {
			continue
		}

		node := ListNode{
			Val:  retArr[i],
			Next: nil,
		}

		lt.Next = &node
		lt = lt.Next
	}


	return ll.Next
}
//leetcode submit region end(Prohibit modification and deletion)


// 将一个数字转换为连表
func getListNode(n int) *ListNode {
	// 将整数串转换为数组
	nStr := strconv.Itoa(n)

	nArr := make([]int, len(nStr)) // 初始化一个数组
	for i,v := range nStr {
		nArr[i] = int(v-'0')
	}

	ll := &ListNode{}
	lt := ll

	for _, v := range nArr {
		node := ListNode{
			Val:  v,
			Next: nil,
		}

		lt.Next = &node
		lt = lt.Next
	}

	return ll.Next
}

func main() {

	list1 := getListNode(7243)
	list2 := getListNode(564)
	addTwoNumbers(list1, list2)
}
